package leetcode.hot100;

import leetcode.common.TreeNode;

@SuppressWarnings("all")
public class _124_二叉树中的最大路径和 {

    /**
     * 路径 被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列
     * 同一个节点在一条路径序列中 至多出现一次
     * 该路径 至少包含一个 节点，且不一定经过根节点
     * 路径和 是路径中各节点值的总和
     * 给你一个二叉树的根节点 root ，返回其 最大路径和
     */
    int maxSum = Integer.MIN_VALUE;

    public int maxPathSum(TreeNode root) {
        // 该函数计算二叉树中的一个节点的最大贡献值
        // 具体而言，就是在以该节点为根节点的子树中寻找以该节点为起点的一条路径，使得该路径上的节点值之和最大
        maxGain(root);
        return maxSum;
    }

    public int maxGain(TreeNode node) {
        // 空节点的最大贡献值等于 0
        if (node == null) {
            return 0;
        }
        // 非空节点的最大贡献值等于节点值与其子节点中的最大贡献值之和（对于叶节点而言，最大贡献值等于节点值）
        // 递归计算左右子节点的最大贡献值
        // 只有在最大贡献值大于 0 时，才会选取对应子节点
        int leftGain = Math.max(maxGain(node.left), 0);
        int rightGain = Math.max(maxGain(node.right), 0);

        // 节点的最大路径和取决于该节点的值与该节点的左右子节点的最大贡献值
        int priceNewPath = node.val + leftGain + rightGain;

        // 更新答案
        maxSum = Math.max(maxSum, priceNewPath);

        // 返回节点的最大贡献值
        return node.val + Math.max(leftGain, rightGain);
    }
}
